๐Ÿ‘ฉโ€๐Ÿ’ป 92342. ์–‘๊ถ๋Œ€ํšŒ

@Seongukbaek Posted July 13, 2022 ยท Updated July 13, 2022 ยท 3 min read

๋ฌธ์ œ

Programmers - ์–‘๊ถ๋Œ€ํšŒ

๐Ÿ“ Logic

private static void dfs(int cnt) { if (cnt == n + 1) { // ์ ์ˆ˜ ๊ณ„์‚ฐ int ryanScore = 0; int apeachScore = 0; for (int i = 0; i <= 10; i++) { if (info[i] == 0 && ryan[i] == 0) continue; if (info[i] < ryan[i]) ryanScore += 10 - i; else apeachScore += 10 - i; } if (ryanScore > apeachScore && ryanScore - apeachScore >= max) { max = ryanScore - apeachScore; answer = ryan.clone(); } return; } // ryan์ด ์œ ํ™”์‚ด์ด info๋ณด๋‹ค ํฌ๋ฉด ์ง„ํ–‰ํ•  ํ•„์š” ์—†์Œ for (int i = 0; i <= 10 && ryan[i] <= info[i]; i++) { ryan[i]++; dfs(cnt + 1); ryan[i]--; } }
  • DFS๋กœ ๋ผ์ด์–ธ์ด ์–ดํ”ผ์น˜๋ณด๋‹ค ํ™”์‚ด์„ ๋งŽ์ด ์˜์ง€ ์•Š์€ ๊ฒฝ์šฐ์— ๋Œ€ํ•ด ํ™”์‚ด์„ ์œ๋‹ค.
  • 1๋ถ€ํ„ฐ n+1๊นŒ์ง€ ์ง„ํ–‰ํ•˜๋ฉด์„œ, ๋ผ์ด์–ธ๊ณผ ์–ดํ”ผ์น˜์˜ ์ ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•˜๊ณ , ์ ์ˆ˜ ์ฐจ๊ฐ€ ํฐ ๊ฒฝ์šฐ๋ฅผ max ์— ๊ฐฑ์‹ ํ•˜๋ฉด์„œ ๋ผ์ด์–ธ์˜ ๊ณผ๋… ์ ์ˆ˜๋ฅผ ๊ฐฑ์‹ ํ•œ๋‹ค.

    • ์ด๋•Œ max ๋ž‘ ๊ฐ™์€ ๊ฒฝ์šฐ์—ฌ๋„ ๊ฐฑ์‹ ํ•˜๋„๋ก ํ•˜์—ฌ, ์ ์ˆ˜ ์ฐจ๊ฐ€ ๊ฐ™์€ ๊ฒฝ์šฐ ๊ฐ€์žฅ ๋‚ฎ์€ ์ ์ˆ˜๋ฅผ ๋งŽ์ด ์œ ๊ฒฝ์šฐ๋กœ ๊ณผ๋… ์ ์ˆ˜๋ฅผ ๊ฐฑ์‹ ํ•  ์ˆ˜ ์žˆ๋„๋ก ํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
class Solution { static int n; static int[] info; static int[] ryan; static int[] answer = new int[]{ -1 }; static int max = 0; public int[] solution(int n, int[] info) { this.n = n; this.info = info; this.ryan = new int[11]; dfs(1); return answer; } private static void dfs(int cnt) { if (cnt == n + 1) { // ์ ์ˆ˜ ๊ณ„์‚ฐ int ryanScore = 0; int apeachScore = 0; for (int i = 0; i <= 10; i++) { if (info[i] == 0 && ryan[i] == 0) continue; if (info[i] < ryan[i]) ryanScore += 10 - i; else apeachScore += 10 - i; } if (ryanScore > apeachScore && ryanScore - apeachScore >= max) { max = ryanScore - apeachScore; answer = ryan.clone(); } return; } // ryan์ด ์œ ํ™”์‚ด์ด info๋ณด๋‹ค ํฌ๋ฉด ์ง„ํ–‰ํ•  ํ•„์š” ์—†์Œ for (int i = 0; i <= 10 && ryan[i] <= info[i]; i++) { ryan[i]++; dfs(cnt + 1); ryan[i]--; } } }

โœ๏ธ Review

  • ์žฌ๊ท€์ ์ธ ๋ฐฉ์‹์œผ๋กœ ๋†’์€ ์ ์ˆ˜๋ถ€ํ„ฐ ํ™”์‚ด์„ ์ด๋ณด๋ฉด์„œ ์ง„ํ–‰ํ•ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ž„์€ ์‰ฝ๊ฒŒ ์•Œ ์ˆ˜ ์žˆ์—ˆ๋‹ค.
  • ์ž์ž˜ํ•œ ๊ตฌํ˜„์—์„œ ๋ง‰ํ˜€ ํ’€์ด๋ฅผ ์ฐธ๊ณ ํ–ˆ๋‹ค.
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€